import java.util.Random;

public class MySort2 {
    public static void main(String[] args) {
        int[] arr1 = {3,44,54,23,67,43,6,78,3,1};
        int[] arr2 = new int[10];
        int[] arr3 = new int[10];
        Random random = new Random();
        for(int j = 10 ; j > 0;j--) {
            arr2[arr2.length - j] = j;
            arr3[arr2.length - j] = random.nextInt(90);
        }

        //testTime(arr1,arr2,arr3);
//        check(arr1);
//        check(arr2);
//        check(arr3);
        /*bubble(arr1);
        bubble(arr2);
        bubble(arr3);*/
        quickSort(arr1,0,arr1.length - 1);
        quickSort(arr2,0,arr2.length - 1);
        quickSort(arr3,0,arr3.length - 1);


        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println(" ");

        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr2[i] + " ");
        }
        System.out.println(" ");
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr3[i] + " ");

        }
        System.out.println();

    }

    //插入排序：
    /*
    时间复杂度:n2;
    空间复杂度：O1
    稳定性：稳定
    * */
    public static void insert(int[] arr){
        for(int i = 1; i < arr.length; i++) {
            int j = i - 1;
            for(;j >= 0; j--) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
                else{
                    break;
                }
            }
        }
    }

    //希尔排序
    /*时间复杂度：n1.3 ~ n1.6;
    空间复杂度：O1；
    稳定性：不稳定；
    * */
    public static void newInsert(int[] arr){
        int gap = arr.length;
        while(gap > 1) {
            gap = gap / 3 + 1;
            insert1(arr,gap);
        }
        insert1(arr,1);
    }
    public static void insert1(int[] arr,int gap){
        for(int i = gap; i < arr.length; i++) {
            int j = i - gap;
            for(;j >= 0; j = j - gap) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
                else{
                    break;
                }
            }
        }
    }
    //选择排序
    public static void check(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            for(int j = i + 1 ; j < arr.length; j++) {
                if(arr[j] < arr[index]){
                    index = j;
                }
            }
            swap(arr, index ,i);
        }
    }

    //冒泡排序
    public static void bubble(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for(int j = 0; j <= i - 1 ; j++) {
                if(arr[j] > arr[j + 1]) {
                    swap(arr,j,j+1);
                }
            }
        }
    }
    //快速排序
    public static void quickSort(int[] arr, int left , int right){
        if(left >= right){
            return;
        }
        //优化2：数组过小时采用插入排序；
        if(right - left < 10) {
            insert2(arr,left ,right);
        }

        //优化1：三数取中
        int result = middle(arr , left ,right);
        swap(arr,result,left);


        int major = quick2(arr,left,right);
        quickSort(arr,left,major - 1 );
        quickSort(arr,major +1  ,right);
    }
    //Hoare法
    public static int quick(int[] arr,int left ,int right) {
        int index = left;
        while(left < right) {
            while(left < right && arr[right] >= arr[index]) {
                right--;
            }
            while (left < right && arr[left] <= arr[index]) {
                left++;
            }
            if(left < right){
            swap(arr,right,left);}
        }
        swap(arr,left,index);
        return left;
    }
    //挖坑法
    public static int quick2(int[] arr,int left ,int right) {
        int tmp = arr[left];
        while(left < right) {
            while (left < right && arr[right] >= tmp) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return  left;
    }



    //插入排序快速排序版
    public static void insert2(int[] arr , int left , int right){
        for(int i = left + 1; i <right; i++) {
            int j = i - 1;
            for(;j >= left; j--) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
                else{
                    break;
                }
            }
        }
    }
    //三数取中法
    public static int middle(int[] arr , int left , int right){
        int middle = (left + right)/2;
        if(arr[middle] > arr[left]){
            if (arr[middle] < arr[right]) {
                return middle;
            } else if (arr[right] < arr[left]) {
                return left;
            }
            else {
                return right;
            }
        }
        if(arr[middle] > arr[right]){
            if (arr[middle] < arr[left]) {
                return middle;
            } else if (arr[left] < arr[right]) {
                return right;
            }
            else {
                return left;
            }
        }
        return  left;
    }


    //交换函数
    public static void swap(int[] arr , int a , int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
    public static void testTime(int[] arr1 ,int[] arr2 , int[] arr3){
        int[] arrA = arr1;
        int[] arrB = arr2;
        int[] arrC = arr3;

        long time1 = System.currentTimeMillis();
        insert(arrA);
        insert(arrB);
        insert(arrC);
        long time2 = System.currentTimeMillis();
        System.out.println(time2 - time1);

         arrA = arr1;
         arrB = arr2;
         arrC = arr3;
        time1 = System.currentTimeMillis();
        newInsert(arrA);
        newInsert(arrB);
        newInsert(arrC);
        time2 = System.currentTimeMillis();
        System.out.println(time2 - time1);


    }
}
